package 贪心算法.k次取反;

import java.util.Arrays;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/2/1 15:28
 * @description:K次取反后的最大化数组和
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {2,-3,-1,5,-4};
        int k = 2;
        System.out.println(largestSumAfterKNegations(arr, k));
    }

    //贪心算法 局部最优，达到全局最优
    public static int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        while (k > 0){
            nums[0] = -nums[0];
            Arrays.sort(nums);
            k--;
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }
}
